package com.test.daily.leetcode.y2021.m10.day1016;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2021/10/16 上午 11:16
 * @version: 1.0
 */
public class Code02_BackTrack02 {
    public String num;
    public int length;
    public int target;
    public List<String> ans;

    public void addOperator(String num, int target) {
        this.num = num;
        this.target = target;
        StringBuffer expr = new StringBuffer();
        ans = new ArrayList<>();
        process(expr, target, 0, 0);

    }

    public void process(StringBuffer expr, int index, long value, long mul) {
        if (index == length) {
            if (value == target) {
                ans.add(expr.toString());
            }
            return;
        }
        if(length > 0){
            expr.append('0');
        }
        int signIndex = expr.length();
        long val = 0;
        for (int j = index; j < length && (j == index || num.charAt(j) != '0'); j++) {
            val = val*10 + num.charAt(j) - '0';
            expr.append(j);
            if(index == 0){
                process(expr,index + 1,value, mul);
            } else {
                expr.setCharAt(signIndex, '+');
                process(expr, index+1, value + mul, mul);
                expr.setCharAt(signIndex, '-');
                process(expr, index+1, value - mul, -mul);
                expr.setCharAt(signIndex, '*');
                process(expr, index+1, value-mul+ val*mul, val*mul);
            }
        }
    }
}
